package leetcode.sword;

class Solution44 {
    public static void main(String[] args) {
        Solution44 s = new Solution44();
        System.out.println(s.findNthDigit(1000000000));
    }
    public int findNthDigit(int n) {
        if(n<10) return n;
        //找n是几位数的区间
        long m = n;
        m += 1; //从10开始计数
        m -= 10; //去掉一位数的占位
        long dig = 2, num = 90, base = 10;
        m -= dig*num; //去掉二位数的占位
        while(m>0){
            dig++;
            num *= 10;
            base *= 10;
            m -= dig*num;
        }
        //dig就是n所指的位数
        m += dig*num; //n在dig位的数的区间内第几个字符
        long bias = m/dig, idx = m%dig; //n指向dig位数的第bias个数（从0）开始，idx表示n指向dig位数的第几位
        if(idx==0){ //到达第bias个数末尾
            bias -= 1;
            idx = dig;
        }
        long res = base + bias; //n指向的数（10进制数）
        //取res的第idx位
        for(int i=1;i<=dig-idx;i++) res/=10;
        return (int)res%10;
    }
}